package backtracking;

import java.util.ArrayList;
import java.util.HashMap;
import java.util.List;
import java.util.Map;

public class LetterCombinationsOfAPhoneNumber17 {
    static Map<Character, Character[]> map = new HashMap<>();

    static {
        map.put('2', new Character[]{'a', 'b', 'c'});
        map.put('3', new Character[]{'d', 'e', 'f'});
        map.put('4', new Character[]{'g', 'h', 'i'});
        map.put('5', new Character[]{'j', 'k', 'l'});
        map.put('6', new Character[]{'m', 'n', 'o'});
        map.put('7', new Character[]{'p', 'q', 'r', 's'});
        map.put('8', new Character[]{'t', 'u', 'v'});
        map.put('9', new Character[]{'w', 'x', 'y', 'z'});
    }

    public List<String> letterCombinations(String digits) {
        List<String> result = new ArrayList<>();
        backTrce(0,digits,result,new StringBuffer());
       return result;
    }

    private void backTrce(int index, String digits, List<String> result, StringBuffer cur) {
        if(index==digits.length()){
            if(cur.length()!=0){
                result.add(cur.toString());
            }
            return;
        }
        char c = digits.charAt(index);
        if(c=='1'){
            backTrce(index+1,digits,result,cur);
        }
        Character[] characters = map.get(c);
        for (int i = 0; i < characters.length; i++) {
            cur.append(characters[i]);
            backTrce(index+1,digits,result,cur);
            cur.deleteCharAt(cur.length()-1);
        }
    }


}
